package com.kevinkk.array;

import java.util.Map;
import java.util.HashMap;

/**
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 */

/**
 * 最经典的滑动窗口题目
 * 这个题目和 FruitIntoBaskets 类似，也是有两2️⃣个维度的信息
 * 首先是字母的种类，另一个是同一个字母的数量，因此也是用一个 Map 来存储这二者之间的关系
 * 首先是统计子串 t 中字母种类和其对应的数量
 *
 * 然后是用滑动窗口的的方式处理字符串 s
 */

public class MinimumWindowSubstring {
    class Solution {
        public String minWindow(String s, String t) {
            char[] sc = s.toCharArray(), tc = t.toCharArray();
            String res = "";
            Map<Character, Integer> smap = new HashMap<>(), tmap = new HashMap<>();
            for (char c : tc)
                tmap.put(c, tmap.getOrDefault(c, 0) + 1);

            // left 和 right 分别表示滑动窗口
            // len 表示满足要求的字母数量
            for (int left = 0, right = 0, len = 0; right < sc.length; right++) {
                int value = smap.getOrDefault(sc[right], 0) + 1;
                smap.put(sc[right], value);
                // 小于等于都符合要求
                if (value <= tmap.getOrDefault(sc[right], 0))
                    len++;

                while (left <= right && smap.get(sc[left]) > tmap.getOrDefault(sc[left], 0)) {
                    smap.put(sc[left], smap.get(sc[left]) - 1);
                    left++;
                }

                if (len == tc.length) {
                    if (res.isEmpty() || res.length() > right - left + 1) {
                        res = s.substring(left, right + 1);
                    }
                }
            }

            return res;

        }
    }


}
